package ricky.quadtree
{
	import flash.geom.Point;
	import flash.geom.Rectangle;
	import flash.utils.Dictionary;

	/**
	 * 线性四叉树
	 */
	public class Quadtree 
	{
		
		public function Quadtree()
		{
			_tree=new Dictionary();
		}

		/**
		 * 得到矩形区域内的所有对象</br>
		 * 参数:</br>
		 * <b>rect:Rectangle</b> 世界坐标矩形区域；
		 */
		public function getRect(rect:Rectangle):Array
		{
			var y:int=int(rect.y/Common.tileHeight);//i
			var x:int=int(rect.x/Common.tileWidth);//j
			var x1:uint=(rect.x+rect.width)/Common.tileWidth;
			var y1:uint=(rect.y+rect.height)/Common.tileHeight;
		
			return getArea(y,y1,x,x1);
		}
		
		/**
		 * 得到格子区域内的所有对象</br>
		 * 参数:</br>
		 * <b>x1:uint</b> (列)垂直开始格子索引</br>
		 * <b>y1:uint</b> (行)水平开始格子索引</br>	
		 * <b>x2:uint</b> (列)垂直结束格子索引</br>	
		 * <b>y2:uint</b> (行)水平结束格子索引</br>	
		 */
		public function getArea(x1:uint,y1:uint,x2:uint,y2:uint):Array
		{
			var mortons:Array;
			var item:Array;
			var result:Array=new Array;
			var m:uint;
			var leaf:Leaf;
			for(var i:uint=y1;i<=y2;i++)
			{
				for(var j:uint=x1;j<=x2;j++)
				{
					m=Morton.morton(i,j);
					leaf=_tree[m];
					if(leaf)
					{
						item=leaf.objects;
						if(item)
						{
							for(var mo:uint=0;mo<item.length;mo++)
							{
								if(result.indexOf(item[mo])==-1)
								{
									result.push(item[mo]);
								}
							}
							
						}
					}
				}
			}
			
			return result;
		}
		
		/**
		 * 得到坐标点周围n格的叶子
		 * 参数:</br>
		 * <b>row:uint</b> (行)</br>	
		 * <b>col:uint</b> (列)</br>
		 * <b>radius:uint</b> 半径</br>		
		 */
		public function getAroundLeaf(row:uint,col:uint,radius:int):Array
		{
			var y1:int,y2:int,x1:int,x2:int;
			
			x1=row-radius;
			y1=col-radius;
			x2=row+radius;
			y2=col+radius;
			if(x1<0)x1=0;
			if(y1<0)y1=0;
			
			var item:Leaf;
			var result:Array=new Array;
			var m:uint;
			for(var i:int=y1;i<=y2;i++)
			{
				for(var j:int=x1;j<=x2;j++)
				{
					m=Morton.morton(i,j);
					item=_tree[m];
					if(item)
						result.push(item);
				}
			}
			
			return result;
		}
		
		/**
		 * 得到m码区域内的所有对象</br>
		 * 参数:</br>
		 * <b>morton1:uint</b> 右上开始格子M码</br>	
		 * <b>morton2:uint</b> 右下结束格子M码</br>	
		 */
		public function getMortonArea(morton1:uint,morton2:uint):Array
		{
			var x1:uint,y1:uint,x2:uint,y2:uint;
			var p1:Array=Morton.unMorton(morton1);
			var p2:Array=Morton.unMorton(morton2);
			var pp1:Point=new Point(p1[1],p1[0]);
			var pp2:Point=new Point(p2[1],p2[0]);
		
			
			if(p1[1]<p2[1] && p1[0]<p2[0])
			{
				y1=p1[0];
				x1=p1[1];
				y2=p2[0];
				x2=p2[1];
			}else
			{
				y1=p2[0];
				x1=p2[1];
				y2=p1[0];
				x2=p1[1];
			}
			
			return this.getArea(x1,y1,x2,y2);
		}
		
		/**
		 * 判断一个点是否在一个区域内
		 * @param m:uint morton码
		 * @param y1:uint (行)水平开始格子索引	
		 * @param y2:uint (行)水平结束格子索引	
		 * @param x1:uint (列)垂直开始格子索引
		 * @param x2:uint (列)垂直结束格子索引	
		 */
		public function checkIn(m:uint,y1:uint,y2:uint,x1:uint,x2:uint):Boolean
		{
			var mij:Array=Morton.unMorton(m);
			var y:Number=mij[0];
			var x:Number=mij[1];
			
			return ( y1<=y && y2>=y && x1<=x && x2>=x);
		}
			
		/**
		 * 通过一维数组创建树
		 * 参数</br>
		 * arr:Array 一维数组
		 * length:int 一维数组宽度
		 */
		public function buildTreeBySingleArray(arr:Array,maxWidth:uint):void
		{
			var traversable:Boolean,y:uint=0,x:uint=0,l:Leaf,arrLen:int,m:uint;
			arrLen=arr.length;
			var att:int=0;
			for(var i:int=0;i<arrLen;i++)
			{
				att=arr[i];
				x=i % maxWidth;
				y=i/maxWidth;

				m=Morton.morton(y,x);
				l=_tree[m];
				if(!l)
				{
					l=new Leaf();
					_tree[m]=l;
				}
				l.x=x;
				l.y=y;
				l.attr=att;
				l.traversable=traversable;
			}
			
		}
		
		/**
		 * 创建树
		 * 参数</br>
		 * arr:Array 二维数组
		 */
		public function buildTree(arr:Array):void
		{
//			_tree=new Dictionary();
			var a0:uint,a1:uint,a2:uint,a3:uint,l:Leaf;
			var item:int=arr[0].length;
			var m:int;
			for(var i:uint=0;i<arr.length;i++) //行
			{
				for(var j:uint=0;j<item;j++)//列
				{
					trace(i+":"+j);
					a0=arr[i][j];				
					l=new Leaf();
					l.attr=a0;
					m=Morton.morton(i,j);	
					l.x=i;
					l.y=j;
					_tree[m]=l; 	
				}			
			}
			
			var re:uint=0;
			for(var x:* in tree)
				re++;
			trace("压缩前"+re);
			
			
//			//压缩
//			for(var key:* in tree)
//			{
//				if(key % 4 ==0)
//				{
//					a0=_tree[key].attr;
//					_tree[key].objects=new Array();	//生成容器
//
//					if(_tree[key+1] && _tree[key+2] && _tree[key+3])
//					{
//						a1=_tree[key+1].attr;
//						a2=_tree[key+2].attr;
//						a3=_tree[key+3].attr;
//				
//						if(a0==a1 && a2==a3 && a0==a2) //如果格子相等就删除
//						{
//							delete _tree[key+1];
//							delete _tree[key+2];
//							delete _tree[key+3];
//						}	
//					}					
//				}// end if %4			
//			}// end for
//			
//			
//			re=0;
//			for(var x:* in tree)
//				re++;
//			trace("压缩后"+re);
		}
		
		/**
		 * 得到m码得叶子
		 */
		public function getLeaf(m:uint):Leaf
		{
			return 	tree[m];
		}
		
		/**
		 * 得到叶子对象的所有对象
		 */
		public function getLeafObjcts(m:uint):Array
		{
			var l:Leaf=_tree[m]
			
			if(l && l.objects)
				return l.objects;
			
			return new Array();
		}
		
		/**
		 * 将游戏对象添加到节点
		 * @param game:Pu 游戏对象
		 */
		public function push(obj:*,morton:int):Object
		{
			var l:Leaf=_tree[morton];
			if(!l)
			{
				l=new Leaf();
				var arr:Array=Morton.unMorton(morton);
				l.x=arr[0];
				l.y=arr[1];
				_tree[morton]=l;
			}

			if(obj)
				l.add(obj);
//			else
//				return false;
			
			return l;
		}
		
		/**
		 * 清理数据
		 */
		public function clear():void
		{
			_tree=new Dictionary();
		}
		
		/**
		 * 从节点中删除游戏对象
		 * @param game:Pu 游戏对象
		 */
		public function remove(obj:*,morton:int):Boolean
		{
			var l:Leaf=_tree[morton];
			if(l)
			{
				return l.remove(obj);
			}
			return false;
		}
		
		public function get tree():Dictionary
		{
			return _tree;
		}

		public function set tree(value:Dictionary):void
		{
			_tree = value;
		}

		
		//private
		private var _tree:Dictionary;//所有叶子
		
	}
}